#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<stack>
using namespace std;


#if 0
int trap(vector<int>& height) {
	if (height.size() == 0)
	{
		return 0;
	}
	int sum = 0;
	stack<int> s;
	s.push(0);
	for (int i = 1; i<height.size(); i++)
	{
		if (height[i]<height[s.top()])
		{
			s.push(i);
		}
		else if (height[i] == height[s.top()])
		{
			continue;
		}
		else
		{
			while (!s.empty() && height[i]>height[s.top()])
			{
				int mid = s.top();
				s.pop();
				if (!s.empty())
				{
					int h = min(height[i], height[s.top()]) - height[mid];
					int w = i - s.top() - 1;
					sum += w*h;
				}
			}
		}
		s.push(i);
	}
	return sum;
}
int main()
{
	vector<int> ss{ 5, 5, 1, 7, 1, 1, 5, 2, 7, 6 };
	cout << trap(ss) << endl;
	return 0;
}

int main()
{
	vector<int> ss{ 1, 2, 3, 4, 5 };
	ss.insert(0, 9);
	return 0;
}


int largestRectangleArea(vector<int>& heights) {
	if (heights.size() == 0)
	{
		return 0;
	}
	vector<int> tmp(heights.size() + 2, 0);
	for (int i = 0; i<heights.size(); i++)
	{
		tmp[i + 1] = heights[i];
	}
	int MaxSum = 0;
	stack<int> s;
	s.push(0);
	for (int i = 1; i<tmp.size(); i++)
	{
		if (tmp[i]>tmp[s.top()])
		{
			s.push(i);
		}
		else if (tmp[i] == tmp[s.top()])
		{
			s.pop();
			s.push(i);
		}
		else
		{
			while (!s.empty() && tmp[i]<tmp[s.top()])
			{
				int mid = s.top();
				s.pop();
				int h = tmp[mid];
				int w = i - s.top() - 1;
				MaxSum = max(MaxSum, h*w);
			}
			s.push(i);
		}
	}
	return MaxSum;
}
int main()
{
	vector<int> ss{ 2, 1, 5, 6, 2, 3 };
	cout << largestRectangleArea(ss) << endl;
	return 0;
}


int search(vector<int>& nums, int target) {
	int left = 0, right = nums.size() - 1;
	while (left < right)
	{
		int mid = (left + right) / 2;
		if (nums[mid]>target)
		{
			right = mid-1;
		}
		else if (nums[mid]<target)
		{
			left = mid + 1;
		}
		else
		{
			return mid;
		}
	}
	return -1;
}
int main()
{
	vector<int> nums{ -1, 0, 3, 5, 9, 12 };
	cout << search(nums, 2) << endl;
	return 0;
}

int removeElement(vector<int>& nums, int val) {
	int fast = 0, slow = 0;
	for (; fast<nums.size(); fast++)
	{
		if (nums[fast] != val)
		{
			nums[slow] = nums[fast];
			slow++;
		}
	}
	return slow;
}
#endif

vector<int> sortedSquares(vector<int>& nums) {
	vector<int> arr(nums.size());
	int left = 0, right = nums.size() - 1, len = nums.size() - 1;
	while (left <= right)
	{
		if (nums[left] * nums[left]>nums[right] * nums[right])
		{
			arr[len] = nums[left] * nums[left];
			left++;
		}
		else if (nums[left] * nums[left]<nums[right] * nums[right])
		{
			arr[len] = nums[right] * nums[right];
			right--;
		}
		else
		{
			arr[len] = nums[right] * nums[right];
			arr[len] = nums[right] * nums[right];
			left++, right--;
			len--;
		}
		len--;
	}
	return arr;
}
int main()
{
	vector<int> ss{ -5, 1, 2, 3 };
	vector<int> s = sortedSquares(ss);
	return 0;
}